package com.agile.leetcode.tree.postorder;

import java.util.ArrayList;
import java.util.List;

/**
 * 590. N 叉树的后序遍历
 * 给定一个 N 叉树，返回其节点值的 后序遍历 。
 * <p>
 * N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
 * <p>
 * <p>
 * <p>
 * 进阶：
 * <p>
 * 递归法很简单，你可以使用迭代法完成此题吗?
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：root = [1,null,3,2,4,null,5,6]
 * 输出：[5,6,3,2,4,1]
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 * 输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
 *
 * @Author:ChenZhangKun
 * @Date: 2021/4/2 14:39
 */
public class PostOrder {


    public static void main(String[] args) {
        PostOrder postOrder = new PostOrder();
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        List<Node> list = new ArrayList<>();
        list.add(node5);
        list.add(node6);
        Node node3 = new Node(3, list);
        Node node2 = new Node(2);
        Node node4 = new Node(4);
        List<Node> list1 = new ArrayList<>();
        list1.add(node3);
        list1.add(node2);
        list1.add(node4);
        Node node1 = new Node(1, list1);
        List<Integer> list2 = postOrder.postOrder(node1);
        System.out.println(list2);
    }

    public List<Integer> postOrder(Node root) {
        List<Integer> list = new ArrayList<>(10);
        postTraverse(root, list);
        return list;
    }

    public void postTraverse(Node node, List<Integer> list) {
        if (node != null) {
            // 拿到子节点
            List<Node> children = node.children;
            // 遍历
            for (Node child : children) {
                if (child.children != null) {
                    // 递归
                    postTraverse(child, list);
                } else {
                    // 加入集合
                    list.add(child.val);
                }
            }
            // 退出时将父节点加入
            list.add(node.val);
        }

    }
}

class Node {
    int val;
    List<Node> children;

    public Node() {
    }

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, List<Node> children) {
        this.val = val;
        this.children = children;
    }
}
